package 剑指offer;

import java.util.HashMap;

public class _39数组中出现次数超过一半的数字 {
	public static void main(String[] args) {
		
		
		
	}
	/**
	 * 
	 *@time 2021年3月11日下午8:48:12
	 * 
	 *@param nums
	 *@return int
	 *
	 *@see Hash法求解
	 */
    public int majorityElement1(int[] nums) {
    	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    	for (int num:nums) {
			if(map.containsKey(num)) {
				map.put(num, map.get(num)+1);
			}else {
				map.put(num, 1);
			}
			
		}
    	int max=nums[0];
    	int maxCount=map.get(nums[0]);
    	for (int num : nums) {
    		int count=map.get(num);
			if(count > maxCount) {
				max=num;
				maxCount=count;
			}
		}
		return max;
    }
    /**
     * 
     *@time 2021年3月11日下午8:51:13
     * 
     *@param nums
     *@return int
     *
     *@see排序求解
     */
    public int majorityElement2(int[] nums) {
    	quickSort(nums, 0, nums.length-1);
    	return nums[nums.length/2];
    }
    private void quickSort(int []arr,int l,int r) {
		if(l>=r) return;
		int i=l,j=r;
		while (i<j) {
			while(i<j&&arr[i] <= arr[l]) i++;
			while(i<j&&arr[j] >= arr[l]) j--;			
			swap(arr, i, j);
		}
		swap(arr, i, l);
		quickSort(arr, l, i);//左边
		quickSort(arr, i+1, r);//右边
	}
    static void swap(int []arr,int a,int b) {
    	int temp = arr[a];
    	arr[a] = arr[b];
    	arr[b] = temp;
    }
    

}
